import java.util.Scanner;

public class PageReplace {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请问您想为进程分配几个物理块？");
        int blockNum = sc.nextInt(); // 物理块数
        int blockArr[] = new int[blockNum]; // 根据物理块数建立物理块数组
        for (int k = 0; k < blockNum; k++) { // 初始化物理块数组
            blockArr[k] = -1; // -1表示当前位置没有页面存放
        }

        // 初始化页面号引用串
        System.out.println("请输入页面号个数：");
        int num=sc.nextInt();
        int arr[]=new int[num];
        System.out.println("请输入页面号队列：");
        for(int i=0;i<num;i++){
            arr[i]=sc.nextInt();
        }

        // 为最近最久未使用算法做准备
        int time[] = new int[blockNum]; // 用数组来判断每个页面上次被调用的时间（即在物理块中的等待时长）

        int timeIndex = 0; // 用于记录哪个页面被调用

        System.out.println("物理块初始化过程：");

        int position = blockNum; // 用于判断物理块什么时候第一次存满
        for (int i = 0; i < arr.length; i++) {
            // 如果说物理块中已经没有空位置，就跳出循环，开始算法
            if (blockArr[blockNum - 1] != -1) {
                break;
            }
            for (int j = 0; j < blockNum; j++) {
                // 只要物理块当前位置没存放页面，就立刻存放新页面
                if (blockArr[j] == -1) {
                    blockArr[j] = arr[i];
                    // 记录当前存放位置的下标，time就不自加这个位置，同时这个位置置0
                    timeIndex = j;
                    time[j] = 0;

                    blockOutput(blockArr);
                    break;
                }

                // 如果遇到了相同的页面，跳过当前页面，记录的编号要向后推移
                if (blockArr[j] == arr[i]) {
                    // position就是为了这种情况准备的，方便后续算法进行循环处理
                    position++;
                    // 记录当前存放位置的下标，time就不自加这个位置，同时这个位置置0
                    timeIndex = j;
                    time[j] = 0;

                    System.out.println("物理块无变化");
                    break;
                }
            }
            for (int m = 0; m < blockNum; m++) {
                if (m == timeIndex) { // 当前操作页面不加1
                    continue;
                }
                // 其他未操作页面，等待时长自加1
                time[m]++;
            }
        }

        // 设立这些tranArr是为了避免blockArr数据被修改
        int tranArr[] = new int[blockNum];
        for(int a = 0; a < blockNum; a++){
            tranArr[a] = blockArr[a];
        }
        System.out.println("");
        System.out.println("物理块初始化的结果：");
        blockOutput(blockArr);
        System.out.println("最佳置换算法：");
        Optimal(arr, tranArr, blockNum, position);   // 最佳置换算法

        int tranArr1[] = new int[blockNum];
        for(int a = 0; a < blockNum; a++){
            tranArr1[a] = blockArr[a];
        }
        System.out.println("");
        System.out.println("物理块初始化的结果：");
        blockOutput(blockArr);
        System.out.println("先进先出算法：");
        FIFO(arr, tranArr1, blockNum, position);      // 先进先出算法

        int tranArr2[] = new int[blockNum];
        for(int a = 0; a < blockNum; a++){
            tranArr2[a] = blockArr[a];
        }
        System.out.println("");
        System.out.println("物理块初始化的结果：");
        blockOutput(blockArr);
        System.out.println("最近最久未使用算法：");
        LRU(arr, tranArr2, blockNum, position, time); // 最近最久未使用算法

    }

    public static void Optimal(int arr[], int blockArr[], int blockNum, int position) {
        int index = 0;     // 用于记录应该被淘汰页面的下标
        int judge = 0;     // 用于记录页面在以后没被访问的最长时间
        int pageExist = 0; // 用于判断页面是否存在于物理块数组中

        // 请求调入页面次数，用于判断缺页率（初始值一定是物理块大小次）
        int requestReplace = blockNum;

        for (int i = position; i < arr.length; i++) {
            // 拿到新页面，首先判断，它是否是物理块中已经存在的页面
            for (int j = 0; j < blockNum; j++) {
                // 如果当前页面存在于物理块中，就去判断下一个页面
                if (arr[i] == blockArr[j]) {
                    System.out.println("物理块无变化");
                    break;
                }
                if (judge == arr.length - 1) {
                    // 如果找到了以后永不使用的页面，就不再判断物理块中其他页面
                    // 因为如果需要淘汰页面，就淘汰这个永不使用的页面即可
                } else {
                    // 找出物理块数组中最应该被替换的页面
                    for (int k = i + 1; k < arr.length; k++) {
                        // 寻找最长时间不被访问的页面
                        if (blockArr[j] == arr[k]) {
                            if (k > judge) { //如果当前页面比上一个页面以后未被使用的时间长
                                index = j;   // 暂且认为当前页面是被淘汰页面，记录它的下标
                                judge = k;   // 更改数值，去和下个满足条件的页面判断
                                break;
                            } else { // 如果当前页面没有上一个页面以后未被使用的时间长，就退出循环
                                break;
                            }
                        }
                        // 如果遍历到原数组的尾部 也没再找到一个和当前页面相同的页面
                        // 那么这个页面肯定是 以后永不使用的页面
                        if (k == arr.length - 1) {
                            index = j; // 记录它的下标
                            judge = k; // 记录它的最值，且当前这个值一定是arr.length-1
                            break;
                        }
                    }
                }
                pageExist++;
                // 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足最佳置换的页面
                if (pageExist == blockNum) {
                    // 通过上面得到的index下标，替换这个需要被淘汰的页面
                    blockArr[index] = arr[i];
                    // 请求调入页面次数加1
                    requestReplace++;

                    blockOutput(blockArr);
                }
            }
            index = 0;     // 归零初始化
            judge = 0;     // 归零初始化
            pageExist = 0; // 归零初始化
        }
        pageMissingRate(requestReplace, arr); // 计算缺页率
    }

    public static void FIFO(int arr[], int blockArr[], int blockNum, int position) {
        int index = 0;     // 用于记录应该被淘汰页面的下标（相当于指针）
        int pageExist = 0; // 用于判断页面是否存在于物理块数组中

        // 请求调入页面次数，用于判断缺页率
        int requestReplace = blockNum;

        for (int i = position; i < arr.length; i++) {
            // 拿到新页面，首先判断，它是否是物理块中已经存在的页面
            for (int j = 0; j < blockNum; j++) {
                // 如果当前页面存在于物理块中，就去判断下一个页面
                if (arr[i] == blockArr[j]) {
                    System.out.println("物理块无变化");
                    break;
                }
                pageExist++;
                // 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足先进先出的页面
                if (pageExist == blockNum) {
                    // 通过上面得到的index下标，替换这个需要被淘汰的页面
                    blockArr[index] = arr[i];
                    // 请求调入页面次数加1
                    requestReplace++;
                    // 指针后移
                    index++;

                    blockOutput(blockArr);
                }
            }
            if (index == blockNum) { // 如果到了物理块尾部，就回到物理块头部
                index = 0;
            }
            pageExist = 0; // 归零初始化
        }
        pageMissingRate(requestReplace, arr); // 计算缺页率
    }

    public static void LRU(int arr[], int blockArr[], int blockNum, int position, int time[]) {
        int index = 0;     // 用于记录被淘汰页面的下标
        int pageExist = 0; // 用于判断页面是否存在于物理块数组中
        int best = 0;      // 用于记录changeArr方法的返回值

        // 请求调入页面次数，用于判断缺页率
        int requestReplace = blockNum;

        for (int i = position; i < arr.length; i++) {
            // 拿到新页面，首先判断，它是否是物理块中已经存在的页面
            for (int j = 0; j < blockNum; j++) {
                // 如果当前页面存在于物理块中，就去判断下一个页面
                if (arr[i] == blockArr[j]) {
                    // 这个位置的页面被调用过，因此重新置0，同时记录下标index，让除了这个下标的其他位置等待时长加1
                    index = j;
                    time[index] = 0;

                    System.out.println("物理块无变化");
                    break;
                }
                pageExist++;
                // 当pageExist的大小变成了物理块大小，意味着当前页面不在物理块中，需要替换掉不满足最近最久未使用的页面
                if (pageExist == blockNum) {
                    // 拿到物理块数组中，最近最久未被使用的页面的下标（即等待时间最长的）
                    best = changeArr(time);
                    // 将这个页面淘汰
                    blockArr[best] = arr[i];
                    // 记录这个淘汰页面的下标，当前新页面重新置0，其他页面等待时长加1
                    index = best;
                    time[index] = 0;
                    // 请求调入页面次数加1
                    requestReplace++;

                    blockOutput(blockArr);
                }
            }
            for (int m = 0; m < blockNum; m++) {
                if (m == index) { // 当前操作页面不加一
                    continue;
                }
                // 其他未操作页面，等待时长自加1
                time[m]++;
            }
            index = 0;     // 归零初始化
            pageExist = 0; // 归零初始化
        }
        pageMissingRate(requestReplace, arr); // 计算缺页率
    }

    public static int changeArr(int time[]) {
        int index = 0; // 记录返回页面的下标
        int best = -1; // 记录最大值变化情况
        for (int i = 0; i < time.length; i++) {
            if (time[i] > best) {
                best = time[i];
                index = i;
            }
        }
        return index;
    }

    public static void blockOutput(int blockArr[]) {
        System.out.print("当前物理块中的页面号：");
        for (int i = 0; i < blockArr.length; i++) {
            System.out.print(blockArr[i] + " ");
        }
        System.out.println("");
    }

    /**
     * 功能：缺页率的计算，缺页率 = 请求调入的次数 / 页面总数
     * */
    public static void pageMissingRate(int num, int arr[]) {
        System.out.print("该算法总共缺页" + num + "次，缺页率为" + (num / (double) arr.length));
        System.out.println("");
    }
}